
"""
题目：求某个模块最短编译时间（python）
已知各个模块编译需要时间与依赖列表
若模块之间存在循环依赖或依赖的模块不存在，则无法进行，返回-1

输入描述：
    第一行是目标模块名。例如"module3"
    以后每行定义一个模块，包括其模块名字、编译时间、依赖的模块名字。例如"module2,10,module1,module3"。

输出描述：
    输出最短编译时间。若无法完成，输出-1。

举例：
    输入：
        module3
        module1,10
        module2,5
        module3,10,module1,module2
    输出：
        20
"""
import json


def time_cost(info: str) -> int:

    data = [x.strip() for x in info.split('\n') if x]

    ###### 第一步：解析文本信息，构造成结构化的字典
    detail = dict()
    for item in data[1:]:
        li = item.split(",")
        detail[li[0]] = {'time': li[1], "depends": li[2:]}

    ###### 第二布，判断输入的数据是否存在循环依赖
    # 2.1首先，定义一个递归函数，用来判断某个module是否存在循环依赖
    existed = []

    def is_loop(module_name: str) -> bool:
        """递归函数，判断某个模块是否存在循环依赖"""

        # 先将当前的进行判断依赖的目标模块进行记录，以备记录完整的依赖路径
        existed.append(module_name)
        # 获取目标模块的对应依赖模块
        depends = detail.get(module_name).get("depends")

        # 如果没有依赖模块，直接返回False
        if not depends:
            return False
        # 如果有依赖模块列表
        else:
            for d in depends:
                # 如果在已经找过的模块列表中存在，说明已经循环依赖了，返回True
                if d in existed:
                    return True

                # 如果依赖模块列表都是全新的，则递归判断是否循环依赖。
                # 但凡其中任何一个元素存在循环依赖则返回True。
            return any(is_loop(d) for d in depends)

    # 2.2 然后遍历数据，检测是否循环依赖。
    # 是则返回-1，程序结束；否则将对应模块的依赖路径更新到detail对象中，key是"dep_path"。
    for module_name in list(detail.keys()):
        # 由于existed是公共变量，在查找每个模块时进行重置。
        existed = []
        if is_loop(module_name):
            return -1
        else:
            # existed[1:] 舍去第0个是因为第0个是自身，这里只需要找依赖的模块即可。
            detail.get(module_name).update({'dep_path': existed[1:]})

    ###### 第三步，开始计算目标模块的耗时
    target = data[0]

    # 获取目标模块的完整依赖
    dep_all = detail.get(target).get("dep_path")
    # 目标模块自身的编译耗时
    self_cost = int(detail.get(target).get("time"))
    # 目标模块的所有依赖的耗时，只取最大值
    dep_cost = max(int(detail.get(m).get("time")) for m in dep_all)

    # 如果目标模块的完整依赖是空则只算自身；否则返回自身和依赖耗时的总和
    return self_cost if not dep_all else self_cost + dep_cost



if __name__ == '__main__':
    info1 = "module3\nmodule1,10\nmodule2,5\nmodule3,10,module1,module2"
    info2 = "module2\nmodule1,10,module3\nmodule2,5\nmodule3,10,module1"
    info3 = "module2\nmodule1,10\nmodule2,5,module3\nmodule3,10,module1,module2"
    info4 = "module1\nmodule1,10,module2\nmodule2,5,module3\nmodule3,10,module1"
    info5 = "module1\nmodule1,10,module2\nmodule2,5,module3\nmodule3,10,module4\nmodule4,20"

    assert time_cost(info1) == 20
    assert time_cost(info2) == -1
    assert time_cost(info3) == -1
    assert time_cost(info4) == -1
    assert time_cost(info5) == 30